package codeRandomThoughts.Test106从中序与后序遍历序列构造二叉树;

import codeRandomThoughts.utils.TreeNode;

import java.time.temporal.Temporal;
import java.util.Arrays;

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //后序数组为空,说明根结点为空
        if (postorder.length == 0) {
            return null;
        }

        //后序数组最后一个元素为根节点
        int rootValue = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootValue);

        //查询根节点在中序数组中的index
        int index = -1;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                index = i;
                break;
            }
        }

        //根据index分割中序数组 分为leftInorder 和 rightInorder
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, index);
        int[] rightInorder = Arrays.copyOfRange(inorder,index+1,inorder.length);

        //根据leftInorder的长度 分割后序数组 分割为 leftPostorder 和 rightPostorder
        int[] leftPostorder = Arrays.copyOfRange(postorder,0,leftInorder.length);
        int[] rightPostorder = Arrays.copyOfRange(postorder,leftInorder.length,postorder.length-1);

        //让根节点的左右子树分别指向递归函数
        root.left = buildTree(leftInorder,leftPostorder);
        root.right = buildTree(rightInorder,rightPostorder);

        //返回根节点
        return  root;
    }

}
